#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double db;
inline ll read() {
	ll x=0,f=1;char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
const ll N=605,Q=1e5+5,inf=0x3f3f3f3f;
int n,m,q,D[N][N],st[N],ed[N],cnt,S,T;
int tot=1,hd[N],dis[N],lst[N],fm[N];
bool vis[N];
struct edge {int to,w,c,nxt;}e[N*N<<1];
void addedge(int x,int y,int w,int c) {e[++tot]={y,w,c,hd[x]};hd[x]=tot;e[++tot]={x,0,-c,hd[y]};hd[y]=tot;}
ll ans[N];
bool spfa() {
	for(int i=1;i<=T;i++) vis[i]=false,dis[i]=inf,lst[i]=fm[i]=0;
	queue <int> q;q.push(S);dis[S]=0;vis[S]=true;
	while(!q.empty()) {
		int nw=q.front();q.pop();vis[nw]=false;
		for(int i=hd[nw];i;i=e[i].nxt) {
			int to=e[i].to,w=e[i].w,c=e[i].c;
			if(w&&dis[nw]+c<dis[to]) dis[to]=dis[nw]+c,lst[to]=nw,fm[to]=i,vis[to]=true,q.push(to);
		}
	}
	return (lst[T]>0);
}
void deal() {
	memset(ans,0x3f3f3f3f,sizeof ans);ans[0]=0;
	for(int i=1;i<=n;i++) {
		if(!spfa()) return ;
		ans[i]=ans[i-1]+dis[T];
		int nw=T;while(nw!=S) e[fm[nw]].w--,e[fm[nw]^1].w++,nw=lst[nw];
	}
}
int main() {
	freopen("journey.in","r",stdin);
	freopen("journey.out","w",stdout);
    n=read(),m=read(),q=read();
    memset(D,0x3f3f3f3f,sizeof D);
    for(int i=1;i<=n;i++) D[i][i]=0;
    for(int i=1;i<=m;i++) {
    	int x=read(),y=read(),w=read();
    	D[x][y]=min(D[x][y],w);
	}
	for(int k=1;k<=n;k++) 
		for(int i=1;i<=n;i++) 
			for(int j=1;j<=n;j++) 
				D[i][j]=min(D[i][j],D[i][k]+D[k][j]);
    for(int i=1;i<=n;i++) st[i]=++cnt;
    for(int i=1;i<=n;i++) ed[i]=++cnt;
    S=++cnt,T=++cnt;
    for(int i=1;i<=n;i++) addedge(S,st[i],1,0),addedge(ed[i],T,1,0);
    for(int i=1;i<=n;i++) 
    	for(int j=1;j<=n;j++) 
    		if(D[i][j]!=inf&&i!=j) addedge(st[i],ed[j],1,D[i][j]);
	deal();
	while(q--) {
		ll C=read(),fnl=inf;
		for(int i=0;i<=n;i++) if(ans[i]!=inf) fnl=min(fnl,ans[i]+C*(n-i));
		cout<<fnl<<'\n';
	}
	return 0;
}